package ink.lovejinhu.swardToOffer;

import java.util.LinkedList;

/**
 * @Author: jin
 * @Date: 2021/9/2 16:42
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Offer_059II {
    LinkedList<Integer> v0 = new LinkedList<Integer>();  //v0维护所有元素
    LinkedList<Integer> v1 = new LinkedList<Integer>();   //v1单调队列  这个队列应该是单调递减

    public Offer_059II() {

    }

    public int max_value() {
        if (v0.isEmpty()) {
            return -1;
        }
        return v1.peekFirst();
    }

    public void push_back(int value) {
        if (v0.isEmpty()) {
            v0.add(value);
            v1.add(value);
        } else {
            while (!v1.isEmpty() && value > v1.peekLast()) {
                v1.pollLast();
            }
            v1.add(value);
            v0.add(value);
        }
    }

    public int pop_front() {
        if (v0.isEmpty()) {
            return -1;
        } else {
            Integer temp = 0;
            if (v0.peekFirst().equals(v1.peekFirst())) {
                temp = v0.peek();
                v0.removeFirst();
                v1.removeFirst();
                return temp;
            } else {
                temp = v0.peek();
                v0.removeFirst();
                return temp;

            }
        }
    }
}
